import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 954. 二倍数对数组
 * <a href="https://leetcode.cn/problems/array-of-doubled-pairs/description/">...</a>
 * User: DELL
 * Date: 2023-10-12
 * Time: 15:26
 */
public class Solution {
    /**
     * 解题思路: (哈希+排序)
     * 设 arr 的长度为 n,题目中的意思本质上就是找 n/2 对数字,使得每一对数字,其中一个数字
     * 是另一个数字的 2 倍,那么首先应该想到的就是将 arr 数组中的所有元素进行哈希,而因为 arr
     * 中的元素可能会重复,因此需要 hashMap,其中 value = key 出现的次数. 这样子做完哈希后,
     * 可以将 hashMap 中的 key 值全部取出来,并排序,排序的依据是根据每个数的绝对值大小,这样子
     * 排完序后,我们只需要从小到大依次遍历每一个 key 值,判断原数组中 2*key 元素的个数是否大于
     * key 元素的个数即可.
     * 该题还可以做完哈希后,提前检查一下 0 的个数是否为偶数个,若不是,直接截断返回 false
     *
     * @param arr
     * @return
     */
    public boolean canReorderDoubled(int[] arr) {
        // 判空处理
        if (arr.length == 0) {
            return true;
        }
        // 使用哈希表存储每个元素出现的次数
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        // 初始化哈希表
        for (int num : arr) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        // 检查 0 的个数是否为偶数
        if ((hashMap.getOrDefault(0, 0) & 1) == 1) {
            return false;
        }
        // 去除 0
        hashMap.remove(0);
        // 去除 key 值,放入 list 中,并根据绝对值进行排序
        List<Integer> list = new LinkedList<>();
        for (int key : hashMap.keySet()) {
            list.add(key);
        }
        Collections.sort(list, (a, b) -> Math.abs(a) - Math.abs(b));
        // 对 list 中的每个 key 进行验证
        for (int key : list) {
            if (hashMap.getOrDefault(2 * key, 0) < hashMap.get(key)) {
                return false;
            }
            hashMap.put(2 * key, hashMap.getOrDefault(2 * key, 0) - hashMap.get(key));
        }
        return true;
    }
}